package inset;

import geom.Line;
import geom.Polygon;
import geom.PolygonList;
import geom.Ray;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Set;

import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.ext.VertexNameProvider;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedWeightedSubgraph;


public class InsetProcessor
{
    class Point implements Comparable
    {
        public Point(Point2D pt, Point2D origin)
        {
            this.pt = pt;
            this.origin = origin;
        }

        protected Point2D pt, origin;

        private double TOL = 1e-12;

        @Override
        public boolean equals(Object obj)
        {
            if (obj != null && obj instanceof Point)
            {
                Point p = (Point) obj;

                return Math.abs(pt.getX() - p.pt.getX()) < TOL && Math.abs(pt.getY() - p.pt.getY()) < TOL;
            }

            return false;
        }

        public int compareTo(Object o)
        {
            if (o != null && o instanceof Point) { return (int) (origin.distanceSq(pt) - origin
                            .distanceSq(((Point) o).pt)); }

            return -1;
        }

        @Override
        public String toString()
        {
            // return "(" + pt.getX() + "," + pt.getY() + ")<" +
            // origin.distance(pt) + ">" + "\n";
            return namer.getVertexName(pt);
        }
    }

    public InsetProcessor(PolygonList polys)
    {
        this.polys = polys;
    }

    public DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> removeCycles()
    {
        DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> g = createGraph();

        namer = new GraphViewer("Removing cycles", g).getNamer();
        // namer = new IntegerNameProvider<Point2D>();

        CycleDetector<Point2D, DefaultWeightedEdge> cd = new CycleDetector<Point2D, DefaultWeightedEdge>(g);

        // List of cycles with potentially smaller elements
        List<List<Point2D>> cycles = cd.findCycles();

        PriorityQueue<List<Point2D>> discoveredCycles = new PriorityQueue<List<Point2D>>(4,
                        new Comparator<Collection<Point2D>>()
                        {
                            public int compare(Collection<Point2D> o1, Collection<Point2D> o2)
                            {
                                return o1.size() - o2.size();
                            }
                        });

        // Try to discover the smallest cycles in the graph
        for (List<Point2D> set : cycles)
        {
            int numSubCyclesAdded = 0;

            for (Point2D point2D : set)
            {
                DirectedWeightedSubgraph<Point2D, DefaultWeightedEdge> sub = new DirectedWeightedSubgraph<Point2D, DefaultWeightedEdge>(
                                g, new HashSet<Point2D>(set), null);
                CycleDetector<Point2D, DefaultWeightedEdge> cdsub = new CycleDetector<Point2D, DefaultWeightedEdge>(sub);
                System.out.println("Examining point: " + namer.getVertexName(point2D));
                List<List<Point2D>> subcycles = cdsub.findCyclesContainingVertex(point2D);

                for (List<Point2D> list : subcycles)
                {
                    if (!list.containsAll(set) && !discoveredCycles.contains(list))
                    {
                        numSubCyclesAdded++;
                        discoveredCycles.add(list);
                    }
                }
            }

            if (numSubCyclesAdded == 0) discoveredCycles.add(set);
        }

        System.out.println(discoveredCycles.size());
        ArrayList<List<Point2D>> removableCycles = new ArrayList<List<Point2D>>(discoveredCycles.size());
        Iterator<List<Point2D>> iter = discoveredCycles.iterator();
        while (iter.hasNext())
        {
            List<Point2D> list = iter.next();

            for (Point2D point2D : list)
            {
                System.out.print(namer.getVertexName(point2D) + ", ");
            }

            System.out.println();

            // Determine if cycle is valid
            Polygon cycle = new Polygon();
            cycle.add(list);

            double cycleDir = cycle.getWindingDirection().ordinal();

            ArrayList<Line> cycleSegs = cycle.getLineSegments();

            // Make sure all lines match the directions from the original input
            // (the weights)
            for (Line line : cycleSegs)
            {
                DefaultWeightedEdge edge = g.getEdge(vm.getVertexForPoint(line.getP1()), vm.getVertexForPoint(line
                                .getP2()));

                if (g.getEdgeWeight(edge) != cycleDir)
                {
                    removableCycles.add(list);
                    break;
                }
            }
        }

        for (List<Point2D> list : removableCycles)
        {
            removeCycle(g, list);
        }

        return g;
    }

    public PolygonList getInset()
    {
        PolygonList inset = new PolygonList();

        DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> g = removeCycles();

        new GraphViewer("Creating polygon", g);

        ConnectivityInspector<Point2D, DefaultWeightedEdge> ci = new ConnectivityInspector<Point2D, DefaultWeightedEdge>(
                        g);

        List<Set<Point2D>> connectedComponents = ci.connectedSets();

        for (Set<Point2D> component : connectedComponents)
        {
            Polygon poly = new Polygon();

            Iterator<Point2D> iter = component.iterator();

            Point2D origin = iter.next(), pt = null;

            poly.moveTo(origin);

            pt = g.getEdgeTarget(g.outgoingEdgesOf(origin).iterator().next());

            poly.lineTo(pt);

            while (!origin.equals(pt))
            {
                pt = g.getEdgeTarget(g.outgoingEdgesOf(pt).iterator().next());
                poly.lineTo(pt);
            }

            poly.close();

            inset.add(poly);
        }

        return inset;
    }

    private void removeCycle(DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> g, List<Point2D> list)
    {
        for (int i = 0; i < list.size(); i++)
        {
            DefaultWeightedEdge edge = g.removeEdge(vm.getVertexForPoint(list.get(i)), vm.getVertexForPoint(list
                            .get((i + 1) % list.size())));

             System.out.println("Removed: " +
             namer.getVertexName(g.getEdgeSource(edge)) + " -> " +
             namer.getVertexName(g.getEdgeTarget(edge)));
        }

        // Look for and remove any newly orphaned vertices
        Set<Point2D> vertices = g.vertexSet();
        ArrayList<Point2D> orphanedVertices = new ArrayList<Point2D>();
        for (Point2D vertex : vertices)
        {
            if (g.inDegreeOf(vertex) == 0 && g.outDegreeOf(vertex) == 0) orphanedVertices.add(vertex);
        }

        for (Point2D point2D : orphanedVertices)
            g.removeVertex(point2D);
    }

    /**
     * Creates a graph for every polygon passed in
     * 
     * @return
     */
    public DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> createGraph()
    {
        DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge> g = new DefaultDirectedWeightedGraph<Point2D, DefaultWeightedEdge>(
                        DefaultWeightedEdge.class);

        ArrayList<ArrayList<Line>> edges = removeOverlappingSegments(polys.getAllSegments());

        vm = new VertexManager();

        for (ArrayList<Line> list : edges)
        {
            for (Line edge : list)
            {
                g.addVertex(vm.getVertexForPoint(edge.getP1()));
                g.addVertex(vm.getVertexForPoint(edge.getP2()));
                DefaultWeightedEdge nEdge = g.addEdge(vm.getVertexForPoint(edge.getP1()), vm.getVertexForPoint(edge
                                .getP2()));

                g.setEdgeWeight(nEdge, (double) edge.getWindingDirection().ordinal());
            }
        }

        return g;
    }

    /**
     * Process sets of lines. This should be any lines that should be looked at
     * for connectedness i.e all sub polygons, ones close together, etc.
     */
    private ArrayList<ArrayList<Line>> removeOverlappingSegments(ArrayList<ArrayList<Line>> segs)
    {
        ArrayList<Intersection> intersections = new ArrayList<Intersection>();

        for (ArrayList<Line> list : segs)
        {
            for (Line l1 : list)
            {
                for (ArrayList<Line> list2 : segs)
                {
                    for (Line l2 : list2)
                    {
                        if (!l1.equals(l2))
                        {
                            Ray r1 = new Ray(l1);
                            Ray r2 = new Ray(l2);

                            Point2D intersection = r1.intersects(r2);

                            if (intersection != null && l1.ptSegDistSq(intersection) <= 1e-10
                                            && l2.ptSegDistSq(intersection) <= 1e-10)
                            {
                                if (!comparePts(intersection, l1.getP1()) && !comparePts(intersection, l1.getP2())
                                                && !comparePts(intersection, l2.getP1())
                                                && !comparePts(intersection, l2.getP2()))
                                {
                                    Intersection i = new Intersection(intersection, l1, l2);

                                    if (!intersections.contains(i)) intersections.add(i);
                                }
                            }
                        }
                    }
                }
            }
        }

        return splitLines(segs, intersections);
    }

    private ArrayList<ArrayList<Line>> splitLines(ArrayList<ArrayList<Line>> lineSegs, ArrayList<Intersection> ints)
    {
        for (ArrayList<Line> list : lineSegs)
        {
            ListIterator<Line> iter = list.listIterator();

            while (iter.hasNext())
            {
                Line l = iter.next();

                PriorityQueue<Point> iPts = new PriorityQueue<Point>();
                //Get the intersections that affect this line
                for (Intersection intersection : ints)
                {
                    if (l.equals(intersection.l1) || l.equals(intersection.l2))
                    {
                        iPts.add(new Point(intersection.pt, l.getP1()));
                    }
                }

                iPts.add(new Point(l.getP2(), l.getP1()));

                //No intersections
                if (iPts.isEmpty()) continue;

                //Split the line into segments
                ArrayList<Line> newSegs = new ArrayList<Line>();

                //p1 since ordered by p1
                Point2D previous = l.getP1();
                while (!iPts.isEmpty())
                {
                    Point newPt = iPts.poll();
                    newSegs.add(new Line(previous, newPt.pt));

                    previous = (Point2D) newPt.pt.clone();
                }

                iter.remove();
                for (Line line2D : newSegs)
                {
                    line2D.setWindingDirection(l.getWindingDirection());
                    iter.add(line2D);
                }
            }
        }

        return lineSegs;
    }

    private boolean comparePts(Point2D p1, Point2D p2)
    {
        return p1.distance(p2) < TOL;
    }

    private static double TOL = 1e-10;

    private PolygonList polys;

    private VertexManager vm;

    private static VertexNameProvider<Point2D> namer;
}
